public class Solution {
    public int[] smallestK(int[] arr, int k) {
        MaxHeap heap = new MaxHeap(k);
        for(int i = 0; i < k ; i++) {
            heap.offer(arr[i]);
        }
        for(int i = k; i < arr.length; i++) {
            if(heap.peek() > arr[i]) {
                heap.arr[0] = arr[i];
                heap.down(0);
            }
        }
        return heap.arr;
    }

}

//实现一个大顶堆
class MaxHeap {
    int[] arr;
    int size;

    public MaxHeap(int capacity) {
        arr = new int[capacity];
    }

    public MaxHeap(int[] smallestK) {
        this.arr = smallestK;
        this.size = smallestK.length;
    }

    //插入元素
    public boolean offer(int value) {
        if(isFull()) {
            return false;
        }
        int i = size;
        int j = (i - 1) / 2;
        while(i > 0 && arr[j] < value) {
            arr[i] = arr[j];
            i = j;
            j = (i - 1) / 2;
        }
        arr[i] = value;
        size++;
        return true;
    }

    //删除堆顶元素
    public int poll() {
        if(isEmpty()) {
            return 0;
        }
        int ret = arr[0];
        arr[0] = arr[size - 1];
        size--;
        down(0);
        return ret;
    }
    //下潜
    public void down(int i) {
        int left = 2 * i + 1;
        int right = left + 1;
        int max = i;
        if(left < size && arr[left] > arr[max]) {
            max = left;
        }
        if(right < size && arr[right] > arr[max]) {
            max = right;
        }
        if(max != i) {
            swap(max,i);
            down(max);
        }

    }

    //交换
    public void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //获取堆顶元素
    public int peek() {
        if(isEmpty()) {
            return 0;
        }
        return arr[0];
    }

    //判断是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //判断是否为满
    public boolean isFull() {
        return size == arr.length;
    }

}
